﻿//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/?envType=problem-list-v2&envId=depth-first-search

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool findpath(TreeNode* root, TreeNode* x, stack<TreeNode*>& st)
    {
        if (root == nullptr)
            return false;

        st.push(root);

        if (root == x)
            return true;

        if (findpath(root->left, x, st))
            return true;

        if (findpath(root->right, x, st))
            return true;

        //回溯--说明此条路径没有找到我们要的x
        st.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        stack<TreeNode*> pst;
        stack<TreeNode*>qst;
        findpath(root, p, pst);
        findpath(root, q, qst);
        while (pst.size() < qst.size())
        {
            qst.pop();
        }
        while (pst.size() > qst.size())
        {
            pst.pop();
        }
        while (pst.top() != qst.top())
        {
            pst.pop();
            qst.pop();
        }
        return pst.top();

    }
};